Metodi iterativi

prof. Matteo Lugli

Created: 2024-04-21 dom 17:54

Metodo di Bisezione


https://www.youtube.com/watch?v=zkd6CLfNNe8

Idea


Partiamo con due punti che stanno uno sopra e l'altro sotto l'asse delle x della nostra funzione

A ogni iterazione calcoliamo il punto medio dell'intervallo: la nostra soluzione si trovera' sicuramente o a destra o a sinistra del punto medio

La parte giusta e' quella in cui le immagini dei due estremi dell'intervallo continuano ad essere uno sopra e l'altro sotto l'asse delle x.

Codice

import matplotlib.pyplot as plt

def f(x):
        return pow(x,4) - 4*pow(x,2)

l = 1
r = 8
n = 1000
step = (r-l)/n
x = [l + i*step for i in range(n)]
y = [f(xi) for xi in x]
zeri = [0 for xi in x]
plt.plot(x,y)
plt.plot(x,zeri)
m = (l+r)/2
target = f(m)
i = 0
while target != 0:
        if(i == 5):
                break
        if(target * f(l)) < 0:
                r = m
        else:
                l = m
        m = (l+r)/2
        target=f(m)
        i+=1
plt.plot(m,0,'ro')
plt.show()

Metodo di Newton


Idea


Si parte da un punto arbitrario sull'asse delle \(x\).

"Approssimiamo" la funzione in quel punto con una retta, in particolare con la retta che passa per il punto \(f(x)\) e ha pendenza pari a \(f'(x)\).

Il prossimo punto della successione e' il punto in cui la retta interseca l'asse delle \(x\).

I valori della successione \({x_0, x_1, x_2, ...x_k}\) si avvicinano sempre di piu' alla vera radice della funzione.

Codice

import matplotlib.pyplot as plt
def f(x):
        return x**4 - 4*(x**2)


xl = 1
xr = 8
n = 1000
step = (xr-xl)/n
x = [xl + i*step for i in range(n+1)]
y = [f(xi) for xi in x]
print(y)
plt.plot(x,y)
plt.plot(x, [0 for xi in x])
m = (xl + xr) / 2
target = f(m)
while target != 0:
        if f(xl) * f(m) > 0:
                xl = m
        else:
                xr = m
        m = (xr + xl) / 2
        target = f(m)
print("radice: {}, target: {}".format(m,target))
plt.plot(m,target, 'ro')
plt.show()